#include <stdlib.h>
#include <assert.h>

typedef struct hashbucket
{
  unsigned long hashval_hashbucket;
  void * record_hashbucket;
  
  struct hashbucket * next_hashbucket;
  
} hashbucket;

typedef struct hashtable
{
  unsigned long (*hash_cb_hashtable)(void *); /* hash computation callback */
  int (*cmp_cb_hashtable)(void *, void *) ;  /* record comparison callback */
  double growth_factor_hashtable;            /* growth factor */
  
  int is_iterating_hashtable;                /* is there an interator? */
  int nrecords_hashtable;                    /* number of records */
  int nbuckets_hashtable;                    /* number of buckets */
  hashbucket ** ppbuckets_hashtable;         /* pointer to array of buckets */
  
} hashtable;

typedef struct hashiter
{
  hashtable * table_hashiter;                /* underlying hash table */
  int slotnum_hashiter;                      /* slotnum currently working on */
  hashbucket * p_bucket_hashiter;            /* next bucket pointer */
  
} hashiter;

/* returns a new hash table */
void * hashtable_alloc(int initial_len, double growth_factor,
                       unsigned long (*hash_cb)(void *),
                       int (*cmp_cb)(void *, void *))
{
  hashtable * table;

  assert(growth_factor > 1.0);               /* better grow up */
  
  table = (hashtable *)malloc(sizeof(*table)); /* allocate the wrapper */
  
  table->hash_cb_hashtable = hash_cb;        /* copy hash cb from client */
  table->cmp_cb_hashtable = cmp_cb;          /* copy cmp cb from client */
  table->growth_factor_hashtable = growth_factor; /* copy growth factor */

  /* allocate initial buckets */
  table->nbuckets_hashtable = initial_len;   /* initial size */
  table->ppbuckets_hashtable = (hashbucket **)calloc(table->nbuckets_hashtable,
                                                     sizeof(hashbucket *));
  
  /* initialize other elements */
  table->nrecords_hashtable = 0;             /* hash table is empty */
  table->is_iterating_hashtable = 0;         /* we are not iterating */
  
  return table;
}


/* frees the memory for the hash table */
void hashtable_free(void * table)
{
  #define TABLE ((hashtable *) table)
  int i;                                     /* loop counter */

  assert(!TABLE->is_iterating_hashtable);

  /* TODO: free client's memory */

  /* free all the hash chains */
  for (i=0; i<TABLE->nbuckets_hashtable; i++)
  {
    hashbucket * p_curr = TABLE->ppbuckets_hashtable[i];
    while (NULL != p_curr)
    {
      hashbucket * p_next = p_curr->next_hashbucket;
      free(p_curr);
      p_curr = p_next;
    }
  }
  
  free(TABLE->ppbuckets_hashtable);
  free(TABLE);                               /* free the wrapper */

  #undef TABLE
}


/* returns 1 if the key already exists */
int hashtable_insert(void * table, void * record)
{
  #define TABLE ((hashtable *) table)
  unsigned long hashval;                     /* hash value */
  hashbucket ** ppbucket; /* a pointer to a pointer to a hash bucket */

  assert(!TABLE->is_iterating_hashtable);    /* can't insert while iterating */

  hashval = (*TABLE->hash_cb_hashtable)(record); /* compute hash value */

  /* find the first bucket to look in */
  ppbucket = TABLE->ppbuckets_hashtable
    + (hashval % TABLE->nbuckets_hashtable);

  /* verify that the record doesn't already exist */
  while (NULL != (*ppbucket))
  {
    if ((hashval == (*ppbucket)->hashval_hashbucket) &&
        (!TABLE->cmp_cb_hashtable(record, (*ppbucket)->record_hashbucket)))
      return 1;                              /* record exists */
    ppbucket = & (*ppbucket)->next_hashbucket;
  }
  /* allocate and populate a new bucket */
  (*ppbucket) = (hashbucket *)malloc(sizeof(hashbucket));
  
  (*ppbucket)->hashval_hashbucket = hashval;
  (*ppbucket)->record_hashbucket = record;
  (*ppbucket)->next_hashbucket = NULL;

  TABLE->nrecords_hashtable ++;              /* one additional element */

  /* if the load is greater than one then rehash */
  if (TABLE->nrecords_hashtable >= TABLE->nbuckets_hashtable)
  {
    int i;                                   /* loop counter */
    int new_nbuckets;
    hashbucket ** new_ppbuckets;
    
    /* allocate new buckets */
    new_nbuckets = (int) (((double) TABLE->nbuckets_hashtable)
                          * TABLE->growth_factor_hashtable);
    new_ppbuckets = (hashbucket **) calloc(new_nbuckets, sizeof(hashbucket *));

    /* move the old buckets to the new ones */
    for (i=0; i<TABLE->nbuckets_hashtable; i++)
    {
      hashbucket * p_bucket = TABLE->ppbuckets_hashtable[i];
      while (NULL != p_bucket)
      {
        hashbucket * p_next = p_bucket->next_hashbucket;
        int newslot = p_bucket->hashval_hashbucket % new_nbuckets;

        /* add this bucket at the head of the new list */
        p_bucket->next_hashbucket = new_ppbuckets[newslot];
        new_ppbuckets[newslot] = p_bucket;
        
        p_bucket = p_next;
      }
    }
    
    /* deallocate the old buckets */
    free(TABLE->ppbuckets_hashtable);
    
    TABLE->ppbuckets_hashtable = new_ppbuckets;
    TABLE->nbuckets_hashtable = new_nbuckets;
  }

  return 0;
  
  #undef TABLE
}


/* returns the record or NULL */
void * hashtable_find(void * table, void * record)
{
  #define TABLE ((hashtable *) table)
  hashbucket * p_bucket;                     /* pointer to a bucket */
  unsigned long hashval;                     /* hash value */

  hashval = (*TABLE->hash_cb_hashtable)(record); /* compute hash value */

  /* find the first bucket to look in */
  p_bucket = TABLE->ppbuckets_hashtable[hashval % TABLE->nbuckets_hashtable];
  
  /* scan all the records in the chain */
  while (NULL != p_bucket)
  {
    if ((hashval == p_bucket->hashval_hashbucket) &&
        (!TABLE->cmp_cb_hashtable(record, p_bucket->record_hashbucket)))
      return p_bucket->record_hashbucket;    /* found */
    p_bucket = p_bucket->next_hashbucket;
  }
  return NULL;
  
  #undef TABLE
}


/* returns the record or NULL if not found */
void * hashtable_delete(void * table, void * record)
{
  #define TABLE ((hashtable *) table)
  unsigned long hashval;                     /* hash value */
  hashbucket ** ppbucket; /* a pointer to a pointer to a hash bucket */

  assert(!TABLE->is_iterating_hashtable);

  hashval = (*TABLE->hash_cb_hashtable)(record); /* compute hash value */

  /* find the first bucket to look in */
  ppbucket = TABLE->ppbuckets_hashtable
    + (hashval % TABLE->nbuckets_hashtable);

  /* scan the chain */
  while (NULL != (*ppbucket))
  {
    if ((hashval == (*ppbucket)->hashval_hashbucket) &&
        (!TABLE->cmp_cb_hashtable(record, (*ppbucket)->record_hashbucket)))
      break;                                 /* found it */
    ppbucket = & (*ppbucket)->next_hashbucket;
  }

  if (NULL != (*ppbucket))
  {
    void * record;
    hashbucket * old = *ppbucket;
    *ppbucket = old->next_hashbucket;
    
    record = old->record_hashbucket;
    
    free(old);
    
    return record;
  }
  else
    return NULL;

  #undef TABLE
}

/* starts an iterator over the hash table, the elements can't be modified */
void * hashtable_itr_start(void * table)
{
  #define TABLE ((hashtable *) table)
  hashiter * iter;

  assert(!TABLE->is_iterating_hashtable);    /* can't already be iterating */
  TABLE->is_iterating_hashtable = 1;

  iter = (hashiter *) malloc(sizeof(hashiter));
  iter->table_hashiter = TABLE;
  iter->slotnum_hashiter = 0;
  iter->p_bucket_hashiter = TABLE->ppbuckets_hashtable[0];
  
  return iter;
  #undef TABLE
}


/* returns the next record from the iterator */
void * hashtable_itr_next(void * iterator)
{
  #define ITER ((hashiter *) iterator)
  hashtable * table = ITER->table_hashiter;
  while (1)
  {
    if (NULL != ITER->p_bucket_hashiter)
    {
      void * record = ITER->p_bucket_hashiter->record_hashbucket;
      ITER->p_bucket_hashiter = ITER->p_bucket_hashiter->next_hashbucket;
      return record;
    }
    
    ITER->slotnum_hashiter ++;               /* next chain */
    if (ITER->slotnum_hashiter < table->nbuckets_hashtable)
      ITER->p_bucket_hashiter = 
        table->ppbuckets_hashtable[ITER->slotnum_hashiter];
    else
      return NULL;
  }
  
  #undef ITER
}


/* end the iteration, the elements can now be modified */
void hashtable_itr_end(void * iterator)
{
  #define ITER ((hashiter *) iterator)
  ITER->table_hashiter->is_iterating_hashtable = 0;
  free(ITER);
  #undef ITER
}


unsigned long hashtable_djb2(unsigned char *str, unsigned long lasthash)
{
  int c;

  if (0 == lasthash)
    lasthash = 5381;
  
  while( (c = *str++) )
    lasthash += (lasthash << 5) + c; /* lasthash * 33 + c */

  return lasthash;
}
